package com.hc.programming.array;

import java.util.Arrays;

/**
 * 34.给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 * 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
 * <p>
 * 示例 1：
 * 输入：nums = [5,7,7,8,8,10], target = 8
 * 输出：[3,4]
 * <p>
 * 示例 2：
 * 输入：nums = [5,7,7,8,8,10], target = 6
 * 输出：[-1,-1]
 * <p>
 * 示例 3：
 * 输入：nums = [], target = 0
 * 输出：[-1,-1]
 * <p>
 * 提示：
 * 0 <= nums.length <= 10^5
 * -10^9 <= nums[i] <= 10^9
 * nums 是一个非递减数组
 * -10^9 <= target <= 10^9
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/6/12 19:45
 */
public class 在排序数组中查找元素的第一个和最后一个位置 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(searchRange(new int[]{0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 4, 5, 6, 6, 6, 7, 8, 8}, 4)));
    }

    public static int[] searchRange(int[] nums, int target) {
        int[] res = new int[]{-1, -1};
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int idx = (left + right) / 2;
            if (nums[idx] == target) {
                if (idx == 0) {
                    res[0] = idx;
                } else if (idx > 0) { // 往左二分找
                    if (nums[idx - 1] != target) {
                        res[0] = idx;
                    } else {
                        int r2 = idx - 1; // 保证r2始终=target
                        while (left <= r2) {
                            int idx2 = (left + r2) / 2;
                            if (nums[idx2] == target) {
                                if (left == idx2) {
                                    res[0] = idx2;
                                    break;
                                }
                                r2 = idx2;
                            } else if (nums[idx2] < target) {
                                if (r2 - idx2 == 1) {
                                    res[0] = r2;
                                    break;
                                } else {
                                    left = idx2 + 1;
                                }
                            }
                        }
                    }
                }
                if (idx == nums.length - 1) {
                    res[1] = idx;
                } else if (idx < nums.length - 1) { // 往有二分找
                    if (nums[idx + 1] != target) {
                        res[1] = idx;
                    } else {
                        int l2 = idx + 1; // 保证l2始终=target
                        while (l2 <= right) {
                            int idx2 = (l2 + right + 1) / 2;
                            if (nums[idx2] == target) {
                                if (idx2 == right) {
                                    res[1] = idx2;
                                    break;
                                }
                                l2 = idx2;
                            } else if (nums[idx2] > target) {
                                if (idx2 - l2 == 1) {
                                    res[1] = l2;
                                    break;
                                } else {
                                    right = idx2 - 1;
                                }
                            }
                        }
                    }
                }
                return res;
            }
            if (nums[idx] < target) {
                left = idx + 1;
            } else {
                right = idx - 1;
            }
        }
        return res;
    }
}
